
// 76.最小覆盖子串
class Solution {
public:
    string minWindow(string s, string t) {
        int n = s.size(), m = t.size();
        unordered_map<char, int> tm;
        for (auto x : t)
            tm[x]++;

        unordered_map<char, int> sm;
        int l = 0, count = 0 , l_ret = 0 , r_ret = n;
        for (int r = 0; r < n; r++) {
            sm[s[r]]++;
            if (tm.count(s[r]) && sm[s[r]] == tm[s[r]]) count++;
            while (count == tm.size()) {
                if(r - l + 1 < r_ret - l_ret + 1) r_ret = r , l_ret = l ;
                if(tm.count(s[l]) && sm[s[l]] == tm[s[l]]) count--;
                sm[s[l++]]--;
            }
        }
        return r_ret == n ? "" : s.substr(l_ret , r_ret - l_ret + 1);
    }
};